#define _CRT_SECURE_NO_WARNINGS 1
int searchInsert(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    int middle = (left + right) / 2;
    if (target > nums[right])
    {
        return right + 1;
    }
    if (target == nums[right])
    {
        return right;
    }
    if (target <= nums[left])
    {
        return left;
    }
    while (left < right)
    {
        if (nums[middle] < target)
        {
            left = middle;
            middle = (left + right) / 2;
        }
        if (nums[middle] > target)
        {
            right = middle;
            middle = (left + right) / 2;
        }
        if (nums[middle] == target)
        {
            return middle;
        }
        if (nums[left] < target
            && target < nums[right]
            && left + 1 == right)
        {
            return right;
        }
    }
    return middle;
}